#include <stdlib.h>
#include <string.h>

#include "ai.h"
#include "board.h"
#include "constants.h"
#include "utilities.h"

#include <stdio.h>

int compare_score(const void *a, const void *b)
{
	return ((node *)a) -> score - ((node *)b) -> score;
}

int r_compare_score(const void *a, const void *b)
{
	return ((node *)b) -> score - ((node *)a) -> score;
}

int min_alphabeta(int depth, node * n)
{
    int i, j = 0, k, pruned;
    int create_children = FALSE;
    if (depth == 0)
    {
        return n -> score = evaluate(n -> g);
    }
	pruned = FALSE;
    if (n -> num_children == 0)
    {
        create_children = TRUE;

        // add all its children
        n -> num_children = empty_count(n -> g) * NUM_COMPUTER_CHOICES;
        n -> children = (node**)malloc(n -> num_children * sizeof(node*));
    }

    for (i = 0; i < n -> num_children;)
    {
        for (k = 0; k < NUM_COMPUTER_CHOICES; ++k)
        {
            if (create_children)
            {
                for (; j < n -> g -> length; ++j)
                {
                    if (n -> g -> array[j] == 0)
                        break;
                }

                n -> children[i] = pop_node();
                n -> children[i] -> parent = n;
                n -> children[i] -> g = pop_grid();
                copy_into(n -> g, n -> children[i] -> g);

                n -> children[i] -> g -> array[j] = computer_choices[k];
                n -> children[i] -> last_move = j * NUM_COMPUTER_CHOICES + k;
            }

			if (pruned)
				n -> children[i] -> score = GOOD;
			else
			{
				n -> children[i] -> alpha = n -> alpha;
				n -> children[i] -> beta = n -> beta;
		        n -> beta = min(n -> beta, max_alphabeta(depth - 1, n -> children[i]));
				if (n -> alpha >= n -> beta)
					pruned = TRUE;
			}
            ++i;
        }
        ++j;
    }

	if (pruned)
		n -> score = n -> alpha;
	else
		n -> score = n -> beta;

	qsort(n -> children, n -> num_children, sizeof(node *), &r_compare_score);

    if (n -> g != NULL)
    {
        push_grid(n -> g);
        n -> g = NULL;
    }

    return n -> score;
}

int max_alphabeta(int depth, node * n)
{
    int i, j, pruned;
    if (depth == 0)
    {
        return n -> score = evaluate(n -> g);
    }
    int create_children = FALSE;

    if (n -> children == NULL)
    {
        create_children = TRUE;

        // add all its children
        n -> children = (node**)malloc(4 * sizeof(node*));
		i = 0;
    }
	else
	{
		i = 4 - n -> num_children;
	}

    j = 0;
	pruned = FALSE;
    for (; i < 4; ++i)
    {
        if (create_children)
        {
            n -> children[j] = pop_node();

            n -> children[j] -> parent = n;
            n -> children[j] -> g = pop_grid(); // g should always be NULL
            copy_into(n -> g, n -> children[j] -> g);

            direction_func[i](n -> children[j] -> g);

            // compare the grids
            if (memcmp(n -> g -> grid[0], n -> children[j] -> g -> grid[0], 
                    sizeof(int) * n -> g -> length) == 0)
            {
                push_node(n -> children[j]);
                continue;
            }

            n -> children[j] -> last_move = i;
        }

		if (pruned)
			n -> children[j] -> score = LOSE;
		else
		{
			n -> children[j] -> alpha = n -> alpha;
			n -> children[j] -> beta = n -> beta;
		    n -> alpha = max(n -> alpha, min_alphabeta(depth - 1, n -> children[j]));
			if (n -> alpha >= n -> beta)
				pruned = TRUE;
		}
		j++;
    }
	if (pruned)
		n -> score = n -> beta;
	else
		n -> score = n -> alpha;

	qsort(n -> children, n -> num_children, sizeof(node *), &compare_score);

	n -> num_children = j;

    if (n -> g != NULL)
    {
        push_grid(n -> g);
        n -> g = NULL;
    }

    return n -> score - depth;
}
